1 /*
2 * Copyright (C) 2007 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 package com.google.common.collect;
18
19 import com.google.common.annotations.GwtCompatible;
20
21 import java.util.Collection;
22 import java.util.List;
23 import java.util.Map;
24 import java.util.Set;
25
26 import javax.annotation.Nullable;
27
28 /**
29 * A collection that maps keys to values, similar to {@link Map}, but in which
30 * each key may be associated with <i>multiple</i> values. You can visualize the
31 * contents of a multimap either as a map from keys to <i>nonempty</i>
32 * collections of values:
33 *
34 * <ul>
35 * <li>a → 1, 2
36 * <li>b → 3
37 * </ul>
38 *
39 * ... or as a single "flattened" collection of key-value pairs:
40 *
41 * <ul>
42 * <li>a → 1
43 * <li>a → 2
44 * <li>b → 3
45 * </ul>
46 *
47 * <p><b>Important:</b> although the first interpretation resembles how most
48 * multimaps are <i>implemented</i>, the design of the {@code Multimap} API is
49 * based on the <i>second</i> form. So, using the multimap shown above as an
50 * example, the {@link #size} is {@code 3}, not {@code 2}, and the {@link
51 * #values} collection is {@code [1, 2, 3]}, not {@code [[1, 2], [3]]}. For
52 * those times when the first style is more useful, use the multimap's {@link
53 * #asMap} view (or create a {@code Map<K, Collection<V>>} in the first place).
54 *
55 * <h3>Example</h3>
56 *
57 * <p>The following code: <pre> {@code
58 *
59 * ListMultimap<String, String> multimap = ArrayListMultimap.create();
60 * for (President pres : US_PRESIDENTS_IN_ORDER) {
61 * multimap.put(pres.firstName(), pres.lastName());
62 * }
63 * for (String firstName : multimap.keySet()) {
64 * List<String> lastNames = multimap.get(firstName);
65 * out.println(firstName + ": " + lastNames);
66 * }}</pre>
67 *
68 * ... produces output such as: <pre> {@code
69 *
70 * Zachary: [Taylor]
71 * John: [Adams, Adams, Tyler, Kennedy] // Remember, Quincy!
72 * George: [Washington, Bush, Bush]
73 * Grover: [Cleveland, Cleveland] // Two, non-consecutive terms, rep'ing NJ!
74 * ...}</pre>
75 *
76 * <h3>Views</h3>
77 *
78 * <p>Much of the power of the multimap API comes from the <i>view
79 * collections</i> it provides. These always reflect the latest state of the
80 * multimap itself. When they support modification, the changes are
81 * <i>write-through</i> (they automatically update the backing multimap). These
82 * view collections are:
83 *
84 * <ul>
85 * <li>{@link #asMap}, mentioned above</li>
86 * <li>{@link #keys}, {@link #keySet}, {@link #values}, {@link #entries}, which
87 * are similar to the corresponding view collections of {@link Map}
88 * <li>and, notably, even the collection returned by {@link #get get(key)} is an
89 * active view of the values corresponding to {@code key}
90 * </ul>
91 *
92 * <p>The collections returned by the {@link #replaceValues replaceValues} and
93 * {@link #removeAll removeAll} methods, which contain values that have just
94 * been removed from the multimap, are naturally <i>not</i> views.
95 *
96 * <h3>Subinterfaces</h3>
97 *
98 * <p>Instead of using the {@code Multimap} interface directly, prefer the
99 * subinterfaces {@link ListMultimap} and {@link SetMultimap}. These take their
100 * names from the fact that the collections they return from {@code get} behave
101 * like (and, of course, implement) {@link List} and {@link Set}, respectively.
102 *
103 * <p>For example, the "presidents" code snippet above used a {@code
104 * ListMultimap}; if it had used a {@code SetMultimap} instead, two presidents
105 * would have vanished, and last names might or might not appear in
106 * chronological order.
107 *
108 * <p><b>Warning:</b> instances of type {@code Multimap} may not implement
109 * {@link Object#equals} in the way you expect. Multimaps containing the same
110 * key-value pairs, even in the same order, may or may not be equal and may or
111 * may not have the same {@code hashCode}. The recommended subinterfaces
112 * provide much stronger guarantees.
113 *
114 * <h3>Comparison to a map of collections</h3>
115 *
116 * <p>Multimaps are commonly used in places where a {@code Map<K,
117 * Collection<V>>} would otherwise have appeared. The differences include:
118 *
119 * <ul>
120 * <li>There is no need to populate an empty collection before adding an entry
121 * with {@link #put put}.
122 * <li>{@code get} never returns {@code null}, only an empty collection.
123 * <li>A key is contained in the multimap if and only if it maps to at least
124 * one value. Any operation that causes a key to have zero associated
125 * values has the effect of <i>removing</i> that key from the multimap.
126 * <li>The total entry count is available as {@link #size}.
127 * <li>Many complex operations become easier; for example, {@code
128 * Collections.min(multimap.values())} finds the smallest value across all
129 * keys.
130 * </ul>
131 *
132 * <h3>Implementations</h3>
133 *
134 * <p>As always, prefer the immutable implementations, {@link
135 * ImmutableListMultimap} and {@link ImmutableSetMultimap}. General-purpose
136 * mutable implementations are listed above under "All Known Implementing
137 * Classes". You can also create a <i>custom</i> multimap, backed by any {@code
138 * Map} and {@link Collection} types, using the {@link Multimaps#newMultimap
139 * Multimaps.newMultimap} family of methods. Finally, another popular way to
140 * obtain a multimap is using {@link Multimaps#index Multimaps.index}. See
141 * the {@link Multimaps} class for these and other static utilities related
142 * to multimaps.
143 *
144 * <h3>Other Notes</h3>
145 *
146 * <p>As with {@code Map}, the behavior of a {@code Multimap} is not specified
147 * if key objects already present in the multimap change in a manner that
148 * affects {@code equals} comparisons. Use caution if mutable objects are used
149 * as keys in a {@code Multimap}.
150 *
151 * <p>All methods that modify the multimap are optional. The view collections
152 * returned by the multimap may or may not be modifiable. Any modification
153 * method that is not supported will throw {@link
154 * UnsupportedOperationException}.
155 *
156 * <p>See the Guava User Guide article on <a href=
157 * "http://code.google.com/p/guava-libraries/wiki/NewCollectionTypesExplained#Multimap">
158 * {@code Multimap}</a>.
159 *
160 * @author Jared Levy
161 * @since 2.0 (imported from Google Collections Library)
162 */
163 @GwtCompatible
164 public interface Multimap<K, V> {
165 // Query Operations
166
167 /**
168 * Returns the number of key-value pairs in this multimap.
169 *
170 * <p><b>Note:</b> this method does not return the number of <i>distinct
171 * keys</i> in the multimap, which is given by {@code keySet().size()} or
172 * {@code asMap().size()}. See the opening section of the {@link Multimap}
173 * class documentation for clarification.
174 */
175 int size();
176
177 /**
178 * Returns {@code true} if this multimap contains no key-value pairs.
179 * Equivalent to {@code size() == 0}, but can in some cases be more efficient.
180 */
181 boolean isEmpty();
182
183 /**
184 * Returns {@code true} if this multimap contains at least one key-value pair
185 * with the key {@code key}.
186 */
187 boolean containsKey(@Nullable Object key);
188
189 /**
190 * Returns {@code true} if this multimap contains at least one key-value pair
191 * with the value {@code value}.
192 */
193 boolean containsValue(@Nullable Object value);
194
195 /**
196 * Returns {@code true} if this multimap contains at least one key-value pair
197 * with the key {@code key} and the value {@code value}.
198 */
199 boolean containsEntry(@Nullable Object key, @Nullable Object value);
200
201 // Modification Operations
202
203 /**
204 * Stores a key-value pair in this multimap.
205 *
206 * <p>Some multimap implementations allow duplicate key-value pairs, in which
207 * case {@code put} always adds a new key-value pair and increases the
208 * multimap size by 1. Other implementations prohibit duplicates, and storing
209 * a key-value pair that's already in the multimap has no effect.
210 *
211 * @return {@code true} if the method increased the size of the multimap, or
212 * {@code false} if the multimap already contained the key-value pair and
213 * doesn't allow duplicates
214 */
215 boolean put(@Nullable K key, @Nullable V value);
216
217 /**
218 * Removes a single key-value pair with the key {@code key} and the value
219 * {@code value} from this multimap, if such exists. If multiple key-value
220 * pairs in the multimap fit this description, which one is removed is
221 * unspecified.
222 *
223 * @return {@code true} if the multimap changed
224 */
225 boolean remove(@Nullable Object key, @Nullable Object value);
226
227 // Bulk Operations
228
229 /**
230 * Stores a key-value pair in this multimap for each of {@code values}, all
231 * using the same key, {@code key}. Equivalent to (but expected to be more
232 * efficient than): <pre> {@code
233 *
234 * for (V value : values) {
235 * put(key, value);
236 * }}</pre>
237 *
238 * <p>In particular, this is a no-op if {@code values} is empty.
239 *
240 * @return {@code true} if the multimap changed
241 */
242 boolean putAll(@Nullable K key, Iterable<? extends V> values);
243
244 /**
245 * Stores all key-value pairs of {@code multimap} in this multimap, in the
246 * order returned by {@code multimap.entries()}.
247 *
248 * @return {@code true} if the multimap changed
249 */
250 boolean putAll(Multimap<? extends K, ? extends V> multimap);
251
252 /**
253 * Stores a collection of values with the same key, replacing any existing
254 * values for that key.
255 *
256 * <p>If {@code values} is empty, this is equivalent to
257 * {@link #removeAll(Object) removeAll(key)}.
258 *
259 * @return the collection of replaced values, or an empty collection if no
260 * values were previously associated with the key. The collection
261 * <i>may</i> be modifiable, but updating it will have no effect on the
262 * multimap.
263 */
264 Collection<V> replaceValues(@Nullable K key, Iterable<? extends V> values);
265
266 /**
267 * Removes all values associated with the key {@code key}.
268 *
269 * <p>Once this method returns, {@code key} will not be mapped to any values,
270 * so it will not appear in {@link #keySet()}, {@link #asMap()}, or any other
271 * views.
272 *
273 * @return the values that were removed (possibly empty). The returned
274 * collection <i>may</i> be modifiable, but updating it will have no
275 * effect on the multimap.
276 */
277 Collection<V> removeAll(@Nullable Object key);
278
279 /**
280 * Removes all key-value pairs from the multimap, leaving it {@linkplain
281 * #isEmpty empty}.
282 */
283 void clear();
284
285 // Views
286
287 /**
288 * Returns a view collection of the values associated with {@code key} in this
289 * multimap, if any. Note that when {@code containsKey(key)} is false, this
290 * returns an empty collection, not {@code null}.
291 *
292 * <p>Changes to the returned collection will update the underlying multimap,
293 * and vice versa.
294 */
295 Collection<V> get(@Nullable K key);
296
297 /**
298 * Returns a view collection of all <i>distinct</i> keys contained in this
299 * multimap. Note that the key set contains a key if and only if this multimap
300 * maps that key to at least one value.
301 *
302 * <p>Changes to the returned set will update the underlying multimap, and
303 * vice versa. However, <i>adding</i> to the returned set is not possible.
304 */
305 Set<K> keySet();
306
307 /**
308 * Returns a view collection containing the key from each key-value pair in
309 * this multimap, <i>without</i> collapsing duplicates. This collection has
310 * the same size as this multimap, and {@code keys().count(k) ==
311 * get(k).size()} for all {@code k}.
312 *
313 * <p>Changes to the returned multiset will update the underlying multimap,
314 * and vice versa. However, <i>adding</i> to the returned collection is not
315 * possible.
316 */
317 Multiset<K> keys();
318
319 /**
320 * Returns a view collection containing the <i>value</i> from each key-value
321 * pair contained in this multimap, without collapsing duplicates (so {@code
322 * values().size() == size()}).
323 *
324 * <p>Changes to the returned collection will update the underlying multimap,
325 * and vice versa. However, <i>adding</i> to the returned collection is not
326 * possible.
327 */
328 Collection<V> values();
329
330 /**
331 * Returns a view collection of all key-value pairs contained in this
332 * multimap, as {@link Map.Entry} instances.
333 *
334 * <p>Changes to the returned collection or the entries it contains will
335 * update the underlying multimap, and vice versa. However, <i>adding</i> to
336 * the returned collection is not possible.
337 */
338 Collection<Map.Entry<K, V>> entries();
339
340 /**
341 * Returns a view of this multimap as a {@code Map} from each distinct key
342 * to the nonempty collection of that key's associated values. Note that
343 * {@code this.asMap().get(k)} is equivalent to {@code this.get(k)} only when
344 * {@code k} is a key contained in the multimap; otherwise it returns {@code
345 * null} as opposed to an empty collection.
346 *
347 * <p>Changes to the returned map or the collections that serve as its values
348 * will update the underlying multimap, and vice versa. The map does not
349 * support {@code put} or {@code putAll}, nor do its entries support {@link
350 * Map.Entry#setValue setValue}.
351 */
352 Map<K, Collection<V>> asMap();
353
354 // Comparison and hashing
355
356 /**
357 * Compares the specified object with this multimap for equality. Two
358 * multimaps are equal when their map views, as returned by {@link #asMap},
359 * are also equal.
360 *
361 * <p>In general, two multimaps with identical key-value mappings may or may
362 * not be equal, depending on the implementation. For example, two
363 * {@link SetMultimap} instances with the same key-value mappings are equal,
364 * but equality of two {@link ListMultimap} instances depends on the ordering
365 * of the values for each key.
366 *
367 * <p>A non-empty {@link SetMultimap} cannot be equal to a non-empty
368 * {@link ListMultimap}, since their {@link #asMap} views contain unequal
369 * collections as values. However, any two empty multimaps are equal, because
370 * they both have empty {@link #asMap} views.
371 */
372 @Override
373 boolean equals(@Nullable Object obj);
374
375 /**
376 * Returns the hash code for this multimap.
377 *
378 * <p>The hash code of a multimap is defined as the hash code of the map view,
379 * as returned by {@link Multimap#asMap}.
380 *
381 * <p>In general, two multimaps with identical key-value mappings may or may
382 * not have the same hash codes, depending on the implementation. For
383 * example, two {@link SetMultimap} instances with the same key-value
384 * mappings will have the same {@code hashCode}, but the {@code hashCode}
385 * of {@link ListMultimap} instances depends on the ordering of the values
386 * for each key.
387 */
388 @Override
389 int hashCode();
390 }